# 1012. 至少有 1 位重复的数字
# 给定正整数 n，返回在 [1, n] 范围内具有 至少 1 位 重复数字的正整数的个数。

#  

# 示例 1：

# 输入：n = 20
# 输出：1
# 解释：具有至少 1 位重复数字的正数（<= 20）只有 11 。
# 示例 2：

# 输入：n = 100
# 输出：10
# 解释：具有至少 1 位重复数字的正数（<= 100）有 11，22，33，44，55，66，77，88，99 和 100 。
# 示例 3：

# 输入：n = 1000
# 输出：262
#  

# 提示：

# 1 <= n <= 109


# 来源：力扣（LeetCode）
# 链接：https://leetcode.cn/problems/numbers-with-repeated-digits
# 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。


from time import time
from functools import lru_cache


class Solution:
    def numDupDigitsAtMostN(self, n: int) -> int:
        A = list(map(int, str(n)))
        N = len(A)
        @lru_cache(None)
        def f(i, tight, mask, hasDup):
            if i >= N:
                if hasDup:
                    return 1
                return 0
            upperLimit = A[i] if tight else 9
            ans = 0
            for d in range(upperLimit + 1):
                tight2 = tight and d == upperLimit
                mask2 = mask if mask == 0 and d == 0 else mask | (1 << d)
                hasDup2 = hasDup or (mask & (1 << d))
                ans += f(i + 1, tight2, mask2, hasDup2)
            return ans
        return f(0, True, 0, False)
    
    
if __name__ == '__main__':
    # args = { 'n': 20}
    args = { 'n': 100}
    # args = { 'n': 1000}
    start = time()
    print(Solution().numDupDigitsAtMostN(**args))
    print('='*40)
    print('耗时:', time()*1000 - start*1000, 'ms')